package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-27 16:55
 * @Gitee: https://gitee.com/yxinmiracle
 */


import javafx.util.Pair;

import java.util.*;


public class N叉树的层次遍历 {
    public List<List<Integer>> levelOrder(Node root) {

        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<Pair<Integer, Node>> queue = new LinkedList<>();
        // 初始化第一层的数据
        queue.add(new Pair<>(0, root));
        while (!queue.isEmpty()) {
            // 当队列不为空的时候
            Pair<Integer, Node> poll = queue.poll();//  把对顶层的数据取出
            Integer index = poll.getKey();
            if (index >= ans.size()) ans.add(new ArrayList<>());
            ans.get(index).add(poll.getValue().val); // 将父节点的数据存入到答案队列中
            // 将该节点的子节点都存入到队列中
            for (Node children : poll.getValue().children) {
                queue.add(new Pair<>(index+1,children));
            }
        }
        return ans;
    }

}
